void swap(int*array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

void quicksort(int* array, int start, int end)
{
    if(start+1 >= end) return;
     
    int i, ppos;
    int pivot = array[start];
 
 
    ppos = start;
    for(i = start+1; i<end; i++)
    {
        if(array[i] < pivot)
        {
            swap(array, ppos+1, i);
            swap(array, ppos, ppos+1);
            ppos++;
        }
    }
     
    quicksort(array,start,ppos);
    quicksort(array,ppos+1,end);
 
}

void quicksortRec(int* array, int start, int end){
	
	if(start+1>=end) return ;
	
	int pivot=array[end-1];
	int i=0;
	int j=end-2;
	
	while(i<=j){
		while(array[i]<=pivot && i<=j) i++;
		while(array[j]>=pivot && i<=j) j--;
		if(i<j){
			swap(array, i, j);
			i++;
			j--;
		}	
	}
	swap(array, i, end-1);
	quicksortRec(array, start, i);
	quicksortRec(array, i+1, end);
}

void quickSort(int* array, int size){
	quicksortRec(array, 0, size);
}